package com.ruyuan2020.im.x.MinStack;

class Node{
    int val ;
    int min;
    Node next;

    public Node() {
    }

    public Node(int val, int min) {
        this.val = val;
        this.min = min;
    }
}



//单链表实现(表头作为栈顶)
class MinStack2 {
    private Node dummyHead;

    public MinStack2() {
        dummyHead =new Node();
    }

    //时间复杂度:O(1)
    public void push(int val) {
        int min =val;
        Node head = dummyHead.next;
        if (head!=null&&head.min<val){
            min=head.min;
        }
        Node node = new Node(val, min);
        node.next=dummyHead.next;
        dummyHead.next=node;
    }

    public void pop() {
        Node head = dummyHead.next;
        if (head!=null){
            dummyHead.next=head.next;
            head.next=null;
        }

    }

    public int top() {
        return dummyHead.next.val;
    }

    public int getMin() {
        return dummyHead.next.min;

    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//runtime:3 ms
//memory:43.2 MB
